package arithmetic;

import static utils.ListNodeUtils.printLink;

import utils.ListNodeUtils.ListNode;

/**
 * 链表翻转
 *
 * @author jiangfeng on 2022/3/30
 */
public class ReverseLink {

    


    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;

        printLink(node1);
        // 1 . 普通翻转并返回头.
        //ListNode reserve = reserve(node1);

        //ListNode reserve = twoReverse1(node1);

        // 3: 随机两个节点翻转 // 前::1->2->3->4->5->6-  后:   1->2->5->4->3->6->
        // ListNode reserve = selectReverse(node1,3,5);

        // 4: 两两翻转 非递归版本
         ListNode reserve = twoReverse2(node1);

        printLink(reserve);
    }


    /**
     * 翻转并,返回头
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
     * 两两翻转, 自己的思路.
     * 输入 1 2 3 4 5 6
     * 输出 2 1 3 3 6 5
     * @return
     */
    public static ListNode twoReverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        // A, B ,C
        ListNode next = head.next;
        ListNode temp = next.next;

        // 给B掉头
        next.next = head;
        // 目前的头转向 下一个可以返回的头连起来.
        head.next = twoReverse(temp);
        return next;
    }

    // 参考的答案的.
    public static ListNode twoReverse1(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = head.next;
        // 头的下一个 给新的头
        head.next = twoReverse1(newHead.next);
        // 新的头翻转.
        newHead.next = head;
        return newHead;
    }

    /**
     * 两两翻转2, 非递归版  递归版空间复杂度为n
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
     * @param head
     * @return
     */
    public static ListNode twoReverse2(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        // 定义哑节点, 方便返回头
        ListNode tempHead = new ListNode(-1);
        tempHead.next=head;

        // 定义指针
        ListNode curr = tempHead;
        while (curr.next != null && curr.next.next != null) {
            // curr->1->2 ->3     curr ->2 ->1 ->3
            ListNode temp1 = curr.next;
            ListNode temp2 = temp1.next;

            // 实现翻转.
            curr.next = temp2;
            temp1.next = temp2.next;
            temp2.next =temp1;

            // 步进2, 1在2的后面了
            curr = temp1;
        }
        return tempHead.next;
    }





    public static ListNode selectReverse(ListNode head, int l, int r) {
        // 先记住头节点
        ListNode curr = head;
        // 找到 两个边界节点, 需要减1
        for (int i = 1; i < l - 1; i++) {
            curr = curr.next;
        }
        ListNode tempStart = curr;
        ListNode start = curr.next;
        for (int i = l; i <= r; i++) {
            curr = curr.next;
        }
        ListNode end = curr;
        // 留下结尾的边界
        ListNode tempEnd = end.next;
        // 切断,方便翻转
        end.next = null;
        // 开始翻转
        ListNode reverse = reverse(start);

        //接回去
        tempStart.next = reverse;
        start.next = tempEnd;
        return head;
    }


}
